Search for: All records

A code C ∶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b ∈ {0,1}k with good confidence by randomly querying the encoding x = C(b) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp(O(k)), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp(ko(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k2/log(k)) on the blocklength. In this paper, we prove a near-cubic lower bound of n ≥ Ω(k3/log6(k)) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k. Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices. 

Promise Constraint Satisfaction Problems (PCSPs) are a generalization ofConstraint Satisfaction Problems (CSPs) where each predicate has a strong and aweak form and given a CSP instance, the objective is to distinguish if thestrong form can be satisfied vs. even the weak form cannot be satisfied. Sincetheir formal introduction by Austrin, Guruswami, and H\aa stad, there has beena flurry of works on PCSPs [BBKO19,KO19,WZ20]. The key tool in studying PCSPsis the algebraic framework developed in the context of CSPs where the closureproperties of the satisfying solutions known as the polymorphisms are analyzed. The polymorphisms of PCSPs are much richer than CSPs. In the Boolean case, westill do not know if dichotomy for PCSPs exists analogous to Schaefer'sdichotomy result for CSPs. In this paper, we study a special case of BooleanPCSPs, namely Boolean Ordered PCSPs where the Boolean PCSPs have the predicate$x \leq y$. In the algebraic framework, this is the special case of BooleanPCSPs when the polymorphisms are monotone functions. We prove that BooleanOrdered PCSPs exhibit a computational dichotomy assuming the Rich 2-to-1Conjecture [BKM21] which is a perfect completeness surrogate of the UniqueGames Conjecture. Assuming the Rich 2-to-1 Conjecture, we prove that a Boolean Ordered PCSP canbe solved in polynomial time if for every $\epsilon>0$, it has polymorphismswhere each coordinate has Shapley value at most $\epsilon$, else it is NP-hard.The algorithmic part of our dichotomy is based on a structural lemma thatBoolean monotone functions with each coordinate having low Shapley value havearbitrarily large threshold functions as minors. The hardness part proceeds byshowing that the Shapley value is consistent under a uniformly random 2-to-1minor. Of independent interest, we show that the Shapley value can beinconsistent under an adversarial 2-to-1 minor.